Data replication provides in general availability and data durability in the presence of failures. For example a replicated data store features strong consistency if it displays a behavior of a non-replicated data store in which operations are executed sequentially. However, performance and scalability are major problems.
With the increasing complexity of data-serving systems and an increased criticality of the stored data byzantine-fault tolerance was established as an alternative to crash-fault tolerance since a large spectrum of issues including simple outages, software-bugs, misconfigurations and even intrusions and malware can be masked and grouped together under the term “arbitrary failure” respectively “byzantine failure”.
To implement a robust replicated data store, i.e. guaranteeing correctness under arbitrary failures, in the presence of asynchrony, concurrency and failures, quorum based replication is used. In the non-patent literature of Jean-Philippe Martin, Lorenzo Alvisi, Michael Dahlin: Minimal Byzantine Storage, DISC 2002: 311-325, it is shown that 3f+1 servers have to be used for byzantine-fault tolerance of f arbitrary failures. To read a correct value, a quorum Qr, i.e. a set of servers Qr, queried by a read operation needs to intersect a quorum Qw updated by a write operation in f+1 servers. That could guarantee that there is at least one correct server in the intersection, since at most f may be fail Byzantine. This translates to the following requirement:|Qr|+|Qw|−n>=f+1  (1)wherein n is the total number of servers to be used.
Furthermore, to avoid indefinitely waiting for crashed servers during a read or a write operation the quorums of servers, Qr and Qw can comprise of at most n-f servers. Since at most f servers may be faulty, n-f servers are guaranteed to eventually reply. This translates to the following requirement:|Qr|=|Qw|<=n-f  (2)By combining the two requirements (1) and (2) this leads to:2n−2f−n>=f+1=>n>=3f+1Therefore conventional systems use 3f+1 servers on byzantine fault-tolerant storage.
For example, in the non-patent literature of Alysson Neves Bessani, Miguel P. Correia, Bruno Quaresma, Fernando André, Paulo Sousa: DepSky: dependable and secure storage in a cloud-of-clouds. EuroSys 2011: 31-46, 3f+1 servers or clouds are used to tolerate the failure up to f servers using byzantine quorum-based data replication.
In the further non-patent literature of Miguel Castro, Barbara Liskov: Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20(4): 398-461 (2002) and Dahlia Malkhi, Michael K. Reiter: Byzantine Quorum Systems. Distributed Computing 11(4): 203-213 (1998) other conventional byzantine fault tolerance systems are shown.